# 寻找旋转排序数组中的最小值II: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/submissions/

class Solution:
    def findMin(self, nums: list) -> int:
        """
            这题比第153号算法题难在了有重复元素上了。那么也就是说可能的场景变多了，所以153号的逻辑并不能完全满足所有的场景情况。 其中就是：
            44044444  这样的话，在153的逻辑时，right = mid 跨度太大，就会错过最小值，唯一需要改变的就是当 nums[mid] == nums[right] 时， right -= 1，然后重新计算 mid， 移动一个，减少right跨度太大，错过最小值。
        """
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2
            # 最小值在mid前面
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]: 
                right = mid
            elif nums[mid] == nums[right]:
                right -= 1

        return nums[left]



